Workbench Add-On/Workbench Add-On - Volume 1.iso/DiskUtil/Crunch/XPK/DOCS/FAST.DOC

Text File | 1993-12-06 | 11KB | 259 lines

                    FAST
           A fast LZRW based compression algorithm
                Version 1.03
             Copyright 1993 Christian von Roques



                Legal issues
                ------------

    xpkFAST is (C) Copyright 1993 by Christian von Roques.

    This package may  be freely distributed,  as long as it  is kept in its
original, complete, and   unmodified form.  It    may not  be distributed  by
itself or in a commercial package of any kind without my written permission.

    xpkFAST is distributed in the hope that  it will be useful, but WITHOUT
ANY WARRANTY;  without even  the   implied warranty of    MERCHANTABILITY  or
FITNESS FOR A PARTICULAR PURPOSE.


                Installation
                ------------

    Make sure the directory libs:compressors  does exist and then just copy
xpkFAST.library  to libs:compressors   .  You  also  need to  have  the XPK
package  installed, it    is  available from  several  sources including Fish
disks.


                 Description
                 -----------

    xpkFAST is an  XPK compression sublibrary  whose main purpose is  to be
fast.  The most  interesting part of FAST  is its speedy  compressor, which
makes it predestined for applications which compress about as often as they
decompress.  Good examples  are: backup systems  which make  use  of XPK to
support  compressed backups  or  compressing filesystems.  An  introductory
text  to the concept   of the XPK compression  system  can be  found in the
OVERVIEW document supplied by the standard XPK distribution.

    FAST consists  of      three  parts,  two  compressors  and     a   common
decompressor.  You  can choose between    the two compressors by using FAST.0
up to FAST.89 for the ``speedy'' compressor  and FAST.90 up to FAST.100 for
the ``crawling'' compressor, which is  still faster than NUKE.  The default
mode is FAST.50 which selects the ``speedy'' compressor.

    Following is  a table briefly listing   some comparative statistics for
most of the xpk compression sublibraries.  These are the results of the XPK
standard benchmark  xBench on the  standard  XPK benchmark system  A3000/25
with  SCRAM, using the  AmigaVision executable  as  data.  Note that memory
requirements don't include xpkmaster.library's buffers.  You can get at the
results for other libraries with the help of xQuery.

Method    Mode     Packing   Unpacking   Packing     Unpacking   Compression
         Memory     Memory    Speed       Speed    Ratio
------ -------     -------   ---------   -------     ---------   -----------
FAST    0..79       64K          0K      428 K/s     1055 K/s    32.7%
FAST   80..100      272K          0K       70 K/s     1096 K/s    39.3%

RDCN    0..100       16K          0K      217 K/s      800 K/s    33.2% *

BLZW    0..14        3K          2K      159 K/s      303 K/s    24.4%
BLZW   15..28        7K          4K      141 K/s      328 K/s    29.4%
BLZW   29..42       15K          8K      135 K/s      343 K/s    31.7%
BLZW   43..57       30K         16K      134 K/s      356 K/s    32.4%
BLZW   58..71       60K         32K      139 K/s      364 K/s    32.9%
BLZW   72..85      120K         64K      143 K/s      374 K/s    33.1%
BLZW   86..100      240K        128K      157 K/s      381 K/s    33.7%

NUKE    0..100      192K          0K       35 K/s      613 K/s    45.2%

IMPL    0..10      300K          0K       29 K/s      360 K/s    34.8%
IMPL   11..30      350K          0K       27 K/s      332 K/s    39.8%
IMPL   31..50      400K          0K       20 K/s      314 K/s    43.3%
IMPL   51..75      425K          0K       14 K/s      300 K/s    44.0%
IMPL   76..98      450K          0K    8 K/s      292 K/s    44.2%
IMPL   99..100      450K          0K    6 K/s      291 K/s    44.3%

RLEN    0..100        0K          0K      140 K/s     1043 K/s     4.5%
CBR0    0..100        0K          0K      388 K/s     1833 K/s     3.1% (**)

(*) The results  compiled into  xpkRDCN.library  are wrong!  [The author of
    RDCN did not have access to a Amiga3000/25 with SCRM and had to guess.]
    The results presented here  have been newly measured  and represent the
    behaviour of the xpkRDCN.library V2.2.

(**)Same as (*) for xpkRDCN.library.

    Some Comments to  the above table: Always  remember that these comments
are just an interpretation of the above table. There are probably data files
giving totally different results!

 *  RDCN is FAST's direct competitor, it gives a bit more compression,
    but is significantly slower.
 *  If you need a very fast decompression use FAST.
 *  For symmetric applications use either FAST or BLZW.
    [BLZW is always two to three times slower than FAST, but is better
     in compressing text files.]
 *  Do not use IMPL, NUKE is faster and gives better compression.
 *  Don't expect too much compression from run length compressors like
    RLEN or CBR0.  If you want to use a runlength encoder use CBR0,
    it's much faster than RLEN.


                  Algorithm
                  ---------

    FAST is a member of the LZ77 family  of datacompressors.  Other popular
members  of the LZ77 family  are:  xpkNUKE, PowerPacker, Imploder (xpkIMPL)
and some parts of lha, gzip, zip, zoo, freeze...

    The common thing about all LZ77 compressors is that they store the data
as sequences of <copy>- and  <quote>-items.  FAST uses one `control-bit' to
distinguish between  a <copy>- and a   <quote>-item.  A <quote>-item simply
consists  of one  byte   which  has  to   be placed  into the  outputstream
uninterpreted.   Each <copy>-item consists of  12 bit <distance>- and 4 bit
<length>-information.   <distance> encodes where to  copy _from_.  The 4095
useful   possibilities  are 1..4095(*)  bytes    back in the  outputstream.
<length> encodes _how_many_ bytes to copy.  Possible <length>s range from 3
to 18, which are encoded as 18-<length>.

    The input:    aaaaadadada compresses to: Q(a) C(1,4)  Q(d) C(2,5).  Where
Q(char) is a <quote>-item and means  write a single character 'char' to the
output and the <copy>-item C(dist,len) means copy 'len' bytes, which can be
found 'dist' bytes back in the output, to the output.

    FAST uses two datastreams. That is, the compressed data consists of two
parts, the wordstream and the  bytestream.  The first compressor which used
this technique was xpkNUKE.  The bytestream starts  at the beginning of the
compressed data and the wordstream is stored in  reverse order beginning at
the  end of the  compressed data.  Thus the  compressed data does look like
this: literalsSSDDRROOWW where     small characters denote  literal bytes and
two capital characters are a word from the wordstream.

    If you want to discover more of the internal  workings of xpkFAST just:
``Use the  force!  Read the  source!''  The  best place  to start your tour
through  the  source is     the decompressor  in decompress.s    since    the
decompressor is much simpler than the compressor.

(*)     I could have been using distances of 1..4096, but doing so would
    have added one instruction to the short and thus fast decompressor.


                   History
                   -------

    In April 1991, Ross Williams published his LZRW1 algorithm by
presenting it at the data compression conference.

    The LZRW1-A algorithm is a direct descendant of the LZRW1 algorithm,
improving it a little in both speed and compression.

    FAST  started as a ``port''  of Ross Williams' LZRW1-A C-Implementation
and his 68000-version  of the decompressor to  the Amiga as xpksub-library.
While porting I made some  small changes improving the decompression speed.
I  removed  the feature  of handling  the   case of  noncompressable input,
because the xpkmaster.library takes care of that.  After that, I found some
cute changes which   dramatically improved the    speed  of the decompressor.
These were in detail:

 *  split the compressed data into a word- and a bytestream, removing many
    double byte accesses with a shift in between.
 *  changed the copy loop from a move-dbra loop to 18 moves in a row.
 *  changed the used range from 1..4096 to 0..4095 eliminating one
    instruction in the decompression loop.
 *  removed all bra.s from the inner decompression loop.
 *  totally rewrote the compressor in 68000 assembler.
    + changed the hashfunction to NOT use mul or div.
    + produces the ``new'' format needed by the new decompressor.
    + removed nearly all of the loop control tests by having
      a fast and a safe loop.
    + small code fits into the instructioncache of a 68030.

    Urban Dominik Müller helped me to improve the speed of the compressor
even further, contributing several ideas and  some code.  For details refer
to the source.

V1.00:    release date: 29-Aug-1993

V1.01:    unreleased.  [testversion with four different compressors.]

V1.02:  release date: 12-Sep-1993
  *    quadrupled the HASHSIZE for FAST.80 .. FAST.100 which allowed the
    removal of 2 now unneeded COMPARE_BYTEs to speed up compress_slow.

V1.03:    release date: 17-Oct-1993
  *    major code juggling in compress2.s to squeeze some cycles.
  *    removed the need for a ctrlCtr in compress2.s in favour of doing
    addx.w ctrl,ctrl  bcs.s ctrlFull and ctrl initialized to #1
    instead of rol.w #1,ctrl  dbra ctrlCnt,notFull and ctrl initialized
    to #$0000FFFF


                           "Thank you"s must go to:
                           ------------------------

    Jörg Bublath        <[e-mail]>
    for never getting tired of assembling and testing new versions.

    Urban Dominik Müller    <[e-mail]>
    for providing ideas and code to improve FAST, XPK itself
    and doing various xBenchmarks on his A4000 and A3000.

    Ralph Schmidt        <[e-mail]>
    for providing BAsm and BDebug  [In my opinion the best
    development environment for assembler programs on the Amiga.]
    and doing some batch-xBenchmarks on his A4000.

    Michael van Elst        <[e-mail]>
    for being so couraged to run one of the first alpha versions
    of the crawling mode on his A3000 during a large filetransfer
    --- and crash.

    Markus Illenseer        <[e-mail]>
    for enabling me the remote-use [and once -guru] of his A2000+68030
    and temporarily ripping all the 16Bit FAST RAM out for the sake
    of acurate xBenchmarks.

    Tobias Walter        <[e-mail]>
    for letting me use his A1000 to test 11 totaly different and
    incompatible versions of FAST in one evening.

    Matthias Meixner        <[e-mail]>
    for doing some xBenchmarks when Jörg was `unavailable'.

    Markus Armbruster        <[e-mail]>
    for assisting me in the two weeks search for the
    _nonexistent_ timing-indeterministency-bug.



                  Contact Addresses
                  -----------------

    Ross Williams
    [e-mail]


    Christian von Roques            Christian von Roques
    Forststrasse 71        or        Kastanienweg 4
  D-76131 Karlsruhe                  D-78713 Schramberg
    GERMANY                    GERMANY

    [e-mail] (till end of 1993)    IRCnick: Nescum
    [e-mail]
    [e-mail] (should be valid in 1994 and later)

    If you are mailing me disks, use an MSDOS-filesystem, since I
    DO NOT OWN an Amiga and most unices can read MSDOS-filesystems.


    Urban Dominik Müller
    Schulhausstrasse 83
 CH-6312 Steinhausen
    SCHWEIZ

    [e-mail]            IRCnick: Zop